---
title: "游园安排"
created: 2025-11-28
tags:
  - 算法
---

# 游园安排

## 题目 [游园安排](https://www.lanqiao.cn/paper/3839/problem/1024/)

![[image-b4e0d9e1.png]]

## 思路分析

![[image-0109bd51.png]]

![[image-71453519.png]]

第一次感受到如此无助 发现自己写代码的能力确实不够

思路很容易想 实现的时候卡老半天……

甚至一开始的提取单词都卡了一下 到后面的回溯最长上升子序列又卡住了 只会算长度不知道怎么回溯路径 唉

为什么最后只有3/10  好像是因为有个字典序顺序 这个方法会打乱顺序 然后最后几个案例还有mle tle等等……啧 难搞

## 代码实现

```typescript
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

vector<string> words;

vector<vector<int>> lcs_length(const vector<string>& X, const vector<string>& Y) {
    int m=X.size();
    int n=Y.size();
    vector<vector<int>> dp(m+1,vector<int>(n+1, 0));

    for(int i=1;i<=m;i++) {
        for(int j=1;j<=n;j++) {
            if(X[i-1]==Y[j-1])
                dp[i][j]=dp[i-1][j-1]+1;
            else
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }
    return dp;
}

vector<string> build_lcs(const vector<vector<int>>& dp, const vector<string>& X, const vector<string>& Y) {
    int i = X.size(), j = Y.size();
    vector<string> lcs;
    while(i > 0 && j > 0) {
        if(X[i-1]==Y[j-1]) {
            lcs.push_back(X[i-1]);
            i--;
            j--;
        }
		else if(dp[i-1][j]>dp[i][j-1])
            i--;
        else
            j--;
    }
    reverse(lcs.begin(), lcs.end());
    return lcs;
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    string orig;
    cin >> orig;
    string tmp;
    for(int i = 0; i < orig.size(); i++) {
        if(isupper(orig[i])){
            if(!tmp.empty()) {
                words.push_back(tmp);
            }
            tmp = orig[i];
        }
        else
            tmp += orig[i];
    }
    if(!tmp.empty())
        words.push_back(tmp);

    vector<string> copy = words;
    sort(words.begin(), words.end());

    auto dp = lcs_length(copy, words);
    vector<string> lcs = build_lcs(dp, copy, words);

    for(auto word:lcs)
        cout<<word;

    return 0;
}
```

## 同类题型

## 视频讲解

---
⬅️ [[皮亚诺曲线距离|皮亚诺曲线距离]] 🏠 [[00-冲刺国赛]] ➡️ [[答疑|答疑]]